package com.lfg.leetcode.leetcode200;

import java.util.Arrays;

public class No279numSquares {


    public static void main(String[] args) {
        int ret = numSquares(12);
        System.out.println(ret);
    }

    public static int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int i=1;i<n;i++){
            for(int j=1;;j++){
               int num=  j*j;
               if(num> i){
                   break;
               }
               dp[i] = Math.min(dp[i-num]+1, dp[i]);
            }
        }

        return dp[n];

    }
    public static int numSquares23(int n) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int val = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++) {
                val = Math.min(dp[i-j*j], val);
            }
            dp[i] = val+1;
        }

        return dp[n];
    }


    public static int numSquares2(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i * i <= n; i++) {
            dp[i * i] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                int cnt = dp[i - j * j];
                dp[i] = Math.min(dp[i], cnt + 1);
            }
        }
        return dp[n];
    }

}
